package cn.itcast.zt.leetcode.list;

import cn.itcast.zt.leetcode.element.ListNode;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 链表相关的算法合集
 */
public class List_Algorithm {
    /**
     * 环形链表  141
     * 给你一个链表的头节点 head ，判断链表中是否有环
     */
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) {
            return false ;
        }

        ListNode slow = head ;
        ListNode fast = head.next ;

        while (slow != fast) {
            if (fast == null || fast.next == null) {
                return false ;
            }

            slow = slow.next ;
            fast = fast.next.next ;
        }

        return true ;
    }

    /**
     * 环形链表  142
     * 给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
     */
    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null) {
            return null ;
        }

        ListNode slow = head ;
        ListNode fast = head ;

        while(fast != null) {
            slow = slow.next ;

            if (fast.next != null) {
                fast = fast.next.next ;
            }else {
                return null ;
            }

            if (fast == slow) {
                ListNode ptr = head ;
                while(ptr != slow) {
                    ptr = ptr.next ;
                    slow = slow.next ;
                }

                return ptr ;
            }
        }

        return null ;
    }

    /**
     * 链表相交
     * 给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null
     * @param headA
     * @param headB
     * @return
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode A = headA ;
        ListNode B = headB ;

        while(A != B) {
            A = A == null ? headB : A.next ;
            B = B == null ? headA : B.next ;
        }

        return A ;
    }

    /**
     * 合并两个有序链表 21
     * 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的
     */
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null) {
            return list2 ;
        }

        if (list2 == null) {
            return list1 ;
        }

        ListNode result = new ListNode(0) ;
        ListNode tail = result ;
        while(list1 != null && list2 != null) {
            if (list1.val > list2.val) {
                tail.next = list2 ;
                list2 = list2.next ;
            }else {
                tail.next = list1 ;
                list1 = list1.next ;
            }

            tail = tail.next ;
        }

        if (list1 != null) {
            tail.next = list1 ;
        }

        if (list2 != null) {
            tail.next = list2 ;
        }

        return result.next ;
    }

    /**
     * 反转链表  24
     * 给定单链表的头节点 head ，请反转链表，并返回反转后的链表的头节点
     */
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head ;
        }

        ListNode end = head ;
        ListNode now = null ;

        while(end.next != null) {
            now = head ;
            head = end.next ;
            end.next = head.next ;
            head.next = now ;
        }

        return head ;
    }

    /**
     * 148. 排序链表
     * 给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
     */
    public ListNode sortList(ListNode head) {
        return sortList(head, null) ;
    }

    public ListNode sortList(ListNode head, ListNode tail) {
        if (head == null) {
            return head ;
        }

        if (head.next == tail) {
            head.next = null ;
            return head ;
        }

        ListNode slow = head, fast = head ;
        while(fast != tail) {
            slow =slow.next ;
            fast = fast.next ;

            if (fast != tail) {
                fast = fast.next ;
            }
        }

        ListNode mid = slow ;
        ListNode list1 = sortList(head, mid) ;
        ListNode list2 = sortList(mid, tail) ;

        ListNode sorted = merge(list1, list2) ;
        return sorted ;
    }

    public ListNode merge(ListNode head1, ListNode head2) {
        ListNode dummyHead = new ListNode(0);
        ListNode temp = dummyHead ,temp1 = head1, temp2 = head2;
        while(temp1 != null && temp2 != null) {
            if (temp1.val <= temp2.val) {
                temp.next = temp1 ;
                temp1 = temp1.next ;
            }else {
                temp.next = temp2 ;
                temp2 = temp2.next ;
            }

            temp = temp.next ;
        }

        if (temp1 != null) {
            temp.next = temp1 ;
        }

        if (temp2 != null) {
            temp.next = temp2 ;
        }

        return dummyHead.next ;
    }

    /**
     * 19. 删除链表的倒数第 N 个结点
     */
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head) ;
        Deque<ListNode> stack = new LinkedList<>() ;
        ListNode cur = dummy ;

        while(cur != null) {
            stack.push(cur);
            cur = cur.next ;
        }

        for (int i = 0; i < n; i++) {
            stack.pop() ;
        }

        ListNode prev = stack.peek() ;
        prev.next = prev.next.next ;
        return dummy.next ;
    }

    /**
     * 82. 删除排序链表中的重复元素 II
     */
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null) {
            return head ;
        }

        ListNode dummy = new ListNode(0, head) ;
        ListNode cur = dummy ;
        while(cur.next != null && cur.next.next != null) {
            if (cur.next.val == cur.next.next.val) {
                int val = cur.next.val;
                while(cur.next != null && cur.next.val == val) {
                    cur.next = cur.next.next ;
                }
            }else {
                cur = cur.next ;
            }
        }

        return dummy.next ;
    }
}
